//
// Created by wdq on 22-9-15.
//
#include <iostream>
#include <cstring>

using namespace std;
#define MaxSize 11
bool vistied[MaxSize];


template<typename ElemType>
struct ListNode {
    ElemType value;
    ListNode *next;

    /*!
     * 递归释放空间
     */

    void print() {
        std::cout << value << std::endl;
    }


    ListNode() : value(), next(nullptr) {}


    explicit ListNode(ElemType value) : value(value), next(nullptr) {}

    ListNode(ElemType value, ListNode *next) : value(value), next(next) {}

    ~ListNode() {
        delete next;
    }
};

template<typename ElemType>
struct LinkList {
    ListNode<ElemType> *header;
    int length;

    LinkList() {
        this->header = new ListNode<ElemType>();
        this->length = 0;
    }

    ~LinkList() {
        delete header;
    }

    void insertByHead(ElemType value) {
        ListNode<ElemType> *p = header->next;
        header->next = new ListNode<ElemType>(value, p);
        length++;

    }

    void insertByTail(ElemType value) {
        auto p = header;
        for (; p->next != nullptr; p = p->next);
        p->next = new ListNode<ElemType>(value);
        this->length++;

    }

    ListNode<ElemType> *get(int index) {
        if (index < 0 && index >= this->length) {
            throw std::out_of_range("the index is not legal");
        }
        auto p = header->next;
        for (; p != nullptr && index > 0; p = p->next, index--);
        return p;
    }

    void set(int index, ElemType value) {
        auto p = get(index);
        p->value = value;
    }

    ListNode<ElemType> *find(ElemType value) {
        auto p = header->next;
        for (; p != nullptr; p = p->next) {
            if (p->value == value) {
                break;
            }
        }
        return p;

    }

    void deleteAfter(ListNode<ElemType> *p) {
        if (p == nullptr) {
            return;
        }
        auto q = p->next;
        if (q == nullptr) {
            return;
        }
        p->next = q->next;
        q->next = nullptr;
        delete q;
        this->length--;
    }

    void print() {
        std::cout << "header -> ";
        for (auto p = header->next; p != nullptr; p = p->next) {
            std::cout << p->value << " -> ";
        }
        std::cout << "^" << std::endl;
    }
};

template<typename ElemType>
struct Queue : public LinkList<ElemType> {
    ListNode<ElemType> *tail;

    Queue() : LinkList<ElemType>() {
        this->tail = this->header;
    }

    void enqueue(ElemType value) {
        tail->next = new ListNode<ElemType>(value);
        tail = tail->next;
        this->length++;

    }

    ElemType dequeue() {
        if (isEmpty()) {
            throw std::out_of_range("the queue is empty!");
        }
        auto item = this->header->next->value;
        if (this->length == 1) {
            this->tail = this->header;
        }
        LinkList<ElemType>::deleteAfter(this->header);
        return item;

    }

    bool isEmpty() {
        return this->header->next == nullptr;
    }
};

struct ArcNode {
    char data;
    int adjvex;
    int info;
    ArcNode *nextarc;

    ArcNode(int adjvex, int info, char data) {
        this->data = data;
        this->adjvex = adjvex;
        this->info = info;
        this->nextarc = nullptr;
    }

    void output() const {
        cout << "->" << data << endl;
    }
};

struct VexNode {
    char data{};
    ArcNode *firstarc;

    VexNode() {
        this->firstarc = nullptr;
    }

    void addArc(int adjvex, int info, char vexData) {
        auto *p = new ArcNode(adjvex, info, vexData);
        p->nextarc = firstarc;
        firstarc = p;
    }

    void output() const {
        ArcNode *p = firstarc;
        while (p) {
            cout << data;
            p->output();
            p = p->nextarc;
        }
    }
};

struct ALGraph {
    VexNode *vertices;
    int edgeNum;
    bool isDirected;

    explicit ALGraph(char *names, bool isDirected = true) {
        int length = int(strlen(names));
        this->edgeNum = length;
        this->isDirected = isDirected;
        this->vertices = new VexNode[edgeNum];
        for (int i = 0; i < length; i++) {
            this->vertices[i].data = names[i];

        }
    }

    void addArc(int head, int tail, int weight = 0) const {
        if (!isDirected) {
            vertices[tail].addArc(head, weight, vertices[head].data);
        }
        vertices[head].addArc(tail, weight, vertices[tail].data);

    }

    void output() const {
        for (int i = 0; i < edgeNum; i++) {
            vertices[i].output();
        }
    }
};

void DFS(ALGraph &G, int vex) {
    cout << G.vertices[vex].data << " -> ";
    vistied[vex] = true;
    ArcNode *p = G.vertices[vex].firstarc;
    while (p) {
        int w = p->adjvex;
        if (!vistied[w]) {
            DFS(G, w);
        }
        p = p->nextarc;
    }
}

void BFS(ALGraph &G, int vex) {
    vistied[vex] = true;
    Queue<VexNode *> visitQueue;
    visitQueue.enqueue(&G.vertices[vex]);
    while (!visitQueue.isEmpty()) {
        auto *temp = visitQueue.dequeue();
        cout << temp->data << " -> ";
        auto *p = temp->firstarc;
        while (p) {
            int w = p->adjvex;
            if (!vistied[w]) {
                vistied[w] = true;
                visitQueue.enqueue(&G.vertices[w]);
            }
            p = p->nextarc;
        }

    }

}


int main() {
    ALGraph g("abcdefgh", false);
    g.addArc(0, 2);
    g.addArc(0, 1);
    g.addArc(1, 4);
    g.addArc(1, 3);
    g.addArc(2, 6);
    g.addArc(2, 5);
    g.addArc(3, 7);
    g.addArc(4, 7);

    g.output();
    cout << endl;

    cout << "DFS: " << endl;
    for (int i = 0; i < g.edgeNum; i++) {
        if (!vistied[i]) {
            DFS(g, 0);
            cout << endl;
        }
    }
    memset(vistied, 0, MaxSize);

    cout << "BFS: " << endl;
    for (int i = 0; i < g.edgeNum; i++) {
        if (!vistied[i]) {
            BFS(g, 0);
            cout << endl;
        }
    }

    return 0;
}